The proliferation of digital media such as digital images, audio, video, and text images (documents) has generated significant interest in copyright protection, annotation, and authentication. Watermarking has been identified as a promising mechanism for copyright protection, annotation, and authentication. Watermarking promises the ability to embed inalterable watermark data directly in a digital file. At a later time, the data may be extracted to identify the origin of the digital file and verify its authenticity.
Typically, watermarking is achieved by changing a portion of the visible image. For example, single pixels within an image may be modified or “flipped” in order to transport data. Embedding watermark data in binary images, however, has presented significant challenges as changing pixels in such images is easily noticed.
Nevertheless, numerous data-hiding methods for embedding watermark data in binary documents have been proposed. For example, Min Wu, Edward Tang and Bede Liu, “Data Hiding in Digital Binary Image”, IEEE International Conference on Multimedia and Expo., 2000, pp. 393-396 proposes dividing a document into blocks, and locating the most suitable pixel within each block to embed watermark data. A list, based on the block size, is used to rank the pixels in blocks in order of appropriateness for flipping. Such ranking, however, is quite subjective and may lead to mixed results depending on the image as a whole. Moreover, for small blocks (e.g., 8×8 pixels), it is difficult to find a suitable list to ensure that every block has at least one flippable pixel. As a consequence, the final result is often not pleasing, as less than ideal pixels may be flipped in some blocks, salt-and-pepper noise, or erosion will be created in this case.
Another known scheme is detailed in Yu-Chee Tseng, Yu-Yuan Chen and Hsiang-Kuang Pan, “A Secure Data Hiding Scheme for Binary Images”, IEEE Transactions on communications, Vol. 50, No. 8, pp. 1227-1231, August 2002. The authors propose binary image watermarking by partitioning images into fixed-sized blocks. A secret key and a weight matrix are used to protect the hidden data. Given an image with block size m×n, the scheme can hide as many as └log2(mn+1)┘ bits of data by flipping at most two bits per block. However, the visual effects of the scheme are noticeable because of the randomness used to choose the location for flipping. As a result, the watermarked document appears to be noisy and is not suitable for text document authentication.
Another known scheme detailed in Yu-Chee Tseng and Hsiang-Kuang Pan in IEEE Transactions on Computers, Vol. 51, No. 7, pp. 873-878, 2002, allows bits within the image to be flipped, if the flipped bit is adjacent to another bit that has a value equal to the now-flipped bit. The adjacent bit thus masks the flipping of the information-bearing bit. However, the resulting watermarked binary image looks very noisy and has many protrusions.
All of these known methods, however, minimally preserve the image quality of the watermark data-embedded image. Moreover, many of them require complex calculations.
Another known watermarking method is best suited to binary text documents. In this method, the data is embedded in the 8-connected boundary of a character. Pairs of patterns that are dual to each other are used for watermark embedding and extraction, which makes it easy for the watermark retrieval without referring to the original. However, the available number for each pattern pairs depends on the resolution of the document images, thus the available patterns can be used for the watermark embedding are very limited, and the capacity of the watermark is relatively low. As well, the method is believed to be computationally complex as contour tracing is required for each character and pattern matching is required for watermark embedding and extraction.
Accordingly, an improved computationally simple method of embedding watermark data in binary text and non-text images while preserving image quality is desired.